#include "quicksort.h"

// 构造函数：将输入数据转为 SortBar 并初始化快速排序的第一个任务帧
QuickSort::QuickSort(const QVector<int> &values) {
    for (int v : values) {
        bars.append({v, Qt::lightGray}); // 默认颜色为浅灰色
    }
    if (!bars.isEmpty())
        stack.push({0, bars.size() - 1, 0, 0, 0, 0}); // 初始化栈：排序整个数组
}

// 获取当前排序数据（用于可视化显示）
const QVector<SortBar>& QuickSort::getData() const {
    return bars;
}

// 判断排序是否完成：即栈是否为空
bool QuickSort::isFinished() const {
    return stack.empty();
}

// 获取并清零比较次数
int QuickSort::getAndResetCompareCount() {
    int count = compareCount;
    compareCount = 0;
    return count;
}

// 获取并清零交换次数
int QuickSort::getAndResetSwapCount() {
    int count = swapCount;
    swapCount = 0;
    return count;
}

// 交换 bars 中的两个元素，并记录交换次数
void QuickSort::swapBars(int i, int j) {
    std::swap(bars[i], bars[j]);
    swapCount++;
}

// 重置所有条目的颜色为浅灰色（每一步开始前调用）
void QuickSort::resetColors() {
    for (auto &bar : bars) {
        bar.color = Qt::lightGray;
    }
}

// 返回快速排序的时间复杂度说明
QString QuickSort::getComplexityInfo() const {
    return "平均 O(n log n)，最好 O(n log n)，最坏 O(n²)，空间复杂度 O(log n)";
}

// 设置排序方向（升序或降序）
void QuickSort::setOrder(SortOrder order) {
    sortOrder = order;
}

// 快速排序的单步执行函数：使用栈模拟递归过程
void QuickSort::step() {
    if (stack.empty()) return; // 无任务则返回

    Frame &frame = stack.top(); // 当前处理的帧
    resetColors(); // 每步开始前重置颜色

    int low = frame.low;
    int high = frame.high;

    // 状态 0：初始化当前区间的分区变量
    if (frame.state == 0) {
        frame.pivotIndex = high; // 以末尾元素为 pivot
        frame.i = low;           // i 指向第一个比 pivot 小的元素插入位置
        frame.j = low;           // j 遍历整个区间
        frame.state = 1;
        return;
    }

    // 状态 1：遍历 j 指针进行 partition 操作
    if (frame.state == 1) {
        if (frame.j < high) {
            // 设置颜色用于可视化
            bars[frame.j].color = Qt::red;           // 当前比较项
            bars[frame.pivotIndex].color = Qt::darkBlue; // pivot 元素
            bars[frame.i].color = Qt::green;          // 目标交换位置

            compareCount++;

            // 判断当前元素是否满足条件并执行交换
            if ((sortOrder == SortOrder::Ascending && bars[frame.j].value < bars[frame.pivotIndex].value) ||
                (sortOrder == SortOrder::Descending && bars[frame.j].value > bars[frame.pivotIndex].value)) {
                swapBars(frame.i, frame.j);
                frame.i++; // i 向右移动
            }

            frame.j++; // j 向右扫描下一个元素
            return; // 本次 step 结束
        } else {
            frame.state = 2; // j 扫描完成，准备交换 pivot
        }
    }

    // 状态 2：将 pivot 放到正确的位置
    if (frame.state == 2) {
        swapBars(frame.i, frame.pivotIndex); // pivot 放入 i 位置
        int pivotPos = frame.i; // 记录 pivot 的最终位置
        stack.pop(); // 当前帧处理完毕

        // 将左右子区间分别压入栈中，继续排序
        if (pivotPos - 1 > low)
            stack.push({low, pivotPos - 1, 0, 0, 0, 0});
        if (pivotPos + 1 < high)
            stack.push({pivotPos + 1, high, 0, 0, 0, 0});
        return;
    }
}
